The present invention relates in general to networking technologies and in particular to methods and apparatus for optimizing the transfer of data packets across a work.
Data traffic on the Internet continues to grow at phenomenal rates. Initially designed as low-bandwidth text medium, Internet traffic is now including greater amounts of high-bandwidth traffic, such as pictures, audio & video streaming, video conferencing, and online gaming.
The primary protocol suite of the Internet is TCP/IP, or Transmission Control Protocol/Internet Protocol. TCP/IP is actually two separate protocols that work together, a higher level protocol called Transmission Control Protocol, and a lower level protocol called Internet Protocol. TCP manages the segmentation of a message, file, or data stream (generically “file”) into smaller packets, or segments, that are transmitted across the network from a source device to one or more target devices. When the packets arrive at their destination, packets that are in-order are reassembled with previously received packets, and an acknowledgement is sent back to the source device. IP, on the other hand, handles the address part of each packet so that it arrives at the proper target device.
For example, an application on a source device, such as a web server, may use TCP/IP to transmit information to an application on a target device, such as a web browser. However, since the Internet is connectionless, there is no guaranteed predetermined path from one device on the network to another. There is, therefore, a very high probability that some packets from the same session will be routed differently than others, arriving at their destination in a different order from the order with which they were initially transmitted.
During the initial setup process, prior to the actual transmission of data, TCP/IP adjusts the size of the transmitted packet according to network conditions between the source and target device. If the packet is too small, the network will be unnecessarily congested, and the data will arrive at its destination needlessly late. If the packet size is too large, it will not arrive at its destination at all, and no acknowledgements will be sent back to the source device. If no acknowledgement is received for some time, TCP/IP may reduce the size of the packet and the number of packets sent until acknowledgements are received. Once acknowledgements are received, TCP/IP will begin to increase the packet size and number of packets again to attempt to optimize the data transfer.
In order to account for the variability of packet size, TCP/IP mandates that each packet contain a sequence number and a length. The sequence number is used to order the packets. Generally speaking, the sequence number of the packet corresponds to the order number of the first data byte in the packet within the total transmitted file. For instance, if a file of 2000 bytes were transmitted, and the 2nd packet transmitted has a sequence number of 1000, then 999 bytes have already been sent target device in the first packet.
The length is used to determine the sequence number of the next packet. For instance, if a file of 2000 bytes were transmitted, and the 2nd packet transmitted has a sequence number of 1000, and a length of 500, then the sequence number of the next packet is 1500.
In general, since applications can only assemble and interpret data in the correct sequential order, the target device only forwards to a target application the next expected sequential packet, along with other sequentially contiguous packets located in the memory buffer of the target device.
FIG. 1A shows, in accordance with a prior art technique, a simplified diagram showing a source device 104 transmitting a group of sequenced packets to a target device 116 across a network. In the example of FIG. 1A, target device 116 does not have a memory buffer for any incoming packets. Received packets whose sequence numbers are out of order are simply discarded. The source device 104 simply retransmits the discarded packets to the target device 116, if acknowledgements are not received after a certain period of time.
At time=N (102), source device 104 transmits packet 100 (112), packet 1000 (110), packet 2000 (108), and packet 3000 (106) in sequence, to target device 116, across network 114. Packet 100 (112), with the smallest sequence number that has not been received, is the next expected packet at target device 116.
At a later time=N+1 103, packet 1000 (110) reaches target device 116 prior to the packet 100 (112). Target device 116, having no data buffering mechanism, simply discards packet 1000 (110), and waits for packet 100 (112), which in this example is arriving next. Source device 104, receiving no acknowledgement after a certain period of time from target device 116, simply retransmits packet 1000 (110).
Although relatively easy to implement, this method is problematic because it needlessly floods the network with retransmitted data packets. Not only will the network appear sluggish to the target application, since it must wait an additional amount of time to receive correctly sequenced packets, but the additional traffic will also reduce the overall performance of the network for all other connected devices by increasing congestion.
Referring now to FIG. 1B, another prior art technique is shown in which the target device 116 contains a memory buffer 120. It is simple in the sense that packets are stored in vacant locations in no particularly order. Once the memory buffer 120 is full, any additional packets, other than the next expected packet, are discarded. The next expected packet is forwarded to the target application once it arrives at the target device, or once it is located in the memory buffer 120. A new next expected packet is then determined.
At time=N (132), source device 104 transmits packet 100 (112), packet 1000 (110), packet 2000 (108), and packet 3000 (106) in proper sequence, to target device 116, across network 114. Packet 100 (112) is the next expected packet at target device 116.
At a later time=N+1 133, packet 1000 (110) and packet 3000 (106) reach target device 116 prior to the packet 100 (112). Target device 116, having a memory buffer 120, places packet 1000 (110) in the first available slot, and packet 3000 (106) in the next available slot, and waits for packet 100 (112), which in the example of FIG. 1B is arriving next.
Once packet 100 (112) arrives, it is forwarded to the target application on the target device 116, and a new next expected packet is determined. The target device 116 then scans the entries in the memory buffer 120 for the new next expected packet. If it is located, it too is forwarded to the software application. In this diagram, packet 1000 (110) is the new next expected packet, and has already arrived at the memory buffer 120. The target device 116 would locate and forward packet 1000 (110) to the software application.
Although the use of a memory buffer 120 is an improvement over the implementation of FIG. 1A, there are still disadvantages. The memory buffer 120 still transfers packets in an inefficient manner to the application, since the sequence number of each packet must be continuously re-inspected in the buffer when a new packet arrives at the target device. This re-inspection increases the network latency for the application by slowing the transfer rate of data packets.
In view of the foregoing, it is desirable to come up with methods and apparatus for optimizing the transfer of data packets across a network, in order to improve application performance and reduce unnecessary network congestion.